SOURCE CODE INCLUDED
ABSTRACT
In the fundamental operation in computer science, Graph algorithm is a great tool used to solve problems related to graph theory and this algorithms have wide applications in solving routing problems. For the purpose of this project four algorithms from the many types of graph algorithms were selected which are Dijkstra’s, Bellman-Ford, kruskal and prim’s Algorithm and it application in solving network routing problem was discussed and tested using a hypothetical scenario where results showing the shortest path between data points in a typical communication network was calculated and display using JAVA programming language to implement it on Netbeans IDE 8.2. However, bellman-ford algorithm which is an algorithm that deals with negative edges does not produce the same output as the rest algorithms due to the data used in testing them all which was a limitation in the test.
TABLE OF CONTENT
ContentPage
Title pagei
Declarationii
Approval Pageiii
Dedicationiv
Acknowledgementsv
Table of Contentsvi
List of Figuresvii
List of Tablesviii
Abstractix
CHAPTER ONE: INTRODUCTION
Background of Study1
Statement of the Problem4
Aim and Objectives of the Study5
Justification of the Study5
Scope of the Study6
Definition of Terms6
CHAPTER TWO: LITERATURE REVIEW
2.1Introduction8
2.2Graph Algorithm10
2.2.1Shortest Path Algorithms10
2.2.2Minimum Spanning Trees22
2.3Related Reviews34
CHAPTER THREE: RESEARCH METHODOLOGY
3.1Introduction39
3.2Pseudocode39
3.2.1 Dijkstra’s Algorithm39
3.2.2Bellman-Ford Algorithm40
3.2.3Kruskal’s Algorithm41
3.2.4Prim’s Algorithm42
3.3Tool Used43
3.4Approach Used43
CHAPTER FOUR: IMPLEMENTATION AND RESULT
4.1Introduction44
4.2Hypothesis45
4.3Test45
4.4Result47
4.5Conclusion52
4.6Limitation53
CHAPTER FIVE: SUMMARY, CONCLUSION AND RECOMMENDATION
5.1Summary54
5.2Conclusion54
5.3Recommendation55
5.4Limitation of Study55
REFERENCE56
APPENDIX A57
LIST OF FIGURES
FiguresPages
2.1 Undirected and Directed Graph9
2.2.1Undirected weighted Graph11
2.2.1 Undirected weighted grap with nodes and edges12
2.2.1Dijkstra’s Shortest Path Algorithm16
2.2.1Bellman-Ford Algorithm20
2.2.2Minimum Spanning Tree for Kruskal Algorithm27
2.2.2Minimum Spanning Tree for Prim’s Algorithm32
4.1Typical network graph43
4.3Typical Communication network46
4.4output window showing the shortest path from 0 to 2.48
4.4Output window showing minimum path to reach all data
points using Kruskal’s Algorithm.50
4.4Output window showing minimum path to reach all data
points using Prim’s Algorithm.51
LIST OF TABLES
TablesPages
3.1Pseudocode for Dijkstra’s Algorithm39
3.2Pseudocode for Bellman-Ford Algorithm39
3.3Pseudocode for Kruskal Algorithm40
3.4Pseudocode for Prim’s Algorithm41
4.1Inputs to Dijkstra’s algorithm47
4.2 Inputs given to Dijkstra’s algorithm (Distance)47
4.3Determination of the shortest path Algorithm48
